COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a41.tex[154,phy] \today\hfill}

\bigskip
\line{\bf CS 254\hfill Midterm}
\line{\bf Spring 1986\hfill}
\bigskip
\line{General Instructions.\hfill}

You may use all books and notes. People (preferably teaching staff) may be 
consulted only to interpret the meaning of the questions.
All answers should be shown by logically compelling argument. No
particular type of argument is compulsory; mathematical induction is a
useful tool, for example, but no one is compelled to use it.
Algorithms may be described at a high level, incorporating algorithms from
the book or lectures, by mention, as subroutines. Results that are proved
in the textbook and lectures may be used. The exam totals 100~points; check
that you have all problems. Median scores may be 50 or lower: don't panic,
the problems look hard to other people too.

\bigskip
\disleft 20pt:{\bf (1)}:
[5 points.] There are other regular expressions for the language
$(ab↑{\ast}c)↑{\ast}$, that contain only one asterisk. Find one.

\bigskip
\disleft 20pt:{\bf (2)}:
[10 points.] We want to classify regular expressions according to
whether ($E$)~the languge they describe is empty~($\emptyset$),
($N$)~consists of the empty string only~($\epsilon$), ($F$)~is some
other finite language, or ($I$)~is infinite. Give an algorithm that works
directly on the regular expression (without converting it to a machine).

\bigskip
\disleft 20pt:{\bf (3)}:
[10 points.] Machine $M$ is a 5-state DFM that accepts $a↑{21}b↑{37}$.

\display 40pt:{\bf (A)}:
Can we infer whether $M$ accepts or rejects $a↑{261}b↑{97}$?

\display 40pt:{\bf (B)}:
Can we infer whether $M$ accepts or rejects $a↑{81}b↑{55}$?

\bigskip
\disleft 20pt:{\bf (4)}:
[20 points.]
Present an algorithm that, given the transition table of a DFM that
recognizes language~$L$, and given strings~$x$ and~$y$, tests whether
$x\appL y$ (infix equivalence). The algorithm need not be efficient,
but its simplicity and correctness will endear you to those fine people
who will grade the exam.

\bigskip
\disleft 20pt:{\bf (5)}:
[15 points.]
Let $L$ be the set of strings $u\,bb\,v$ over $\{a,b\}↑{\ast}$ where the
number of $a$'s in~$u$ is a multiple of three, and the number of $a$'s
in~$v$ is a multiple of two. Find the minimized DFM recognizing~$L$.

\bigskip
\disleft 20pt:{\bf (6)}:
[10 points.]
Put the following CFG into Chomsky normal form, with no useless variables:
$$\eqalign{V&=\{S,D,E,F,G,H,I,J,K,L\}\cr
T&=\{a,b,(,),+,-,*,/,\uparrow,\downarrow\}\cr
S&\hbox{ is the root symbol}\cr
P&=\cr}$$
{}
$$\eqalign{S&→E\mid GF\cr
E&→D\mid -D\mid EK\cr
D&→F\mid D*F\mid D/F\cr
F&→a\mid b\mid (E)\mid GI\cr
G&→G\uparrow H\mid H\cr
H&→H\downarrow G\mid GD\cr
I&→*J\cr
J&→E\cr
K&→+DL\mid -DL\mid\epsilon\cr
L&→\epsilon\mid E\cr}$$

\bigskip
\disleft 20pt:{\bf (7)}:
[10 points.]
Give a direct method (not converting to finite machines, for example)
to find a context-free grammar for a language, given a regular expression
for that language.

\bigskip
\disleft 20pt:{\bf (8)}:
[20 points total.]
Modifying the Hopcroft-Ullman definition of a PDM transition slightly,
we say that a transition is a quintuple $\langle q,x,y,z,q'\rangle$
where $q,q'\in Q$; $x\in\Sigma↑{\ast}$; $y,z\in\Gamma↑{\ast}$.
This transition allows the PDM, in one step, from control state~$q$,
to read string~$x$ from the input, pop string~$y$ off the stack, push
string~$z$ on the stack, and enter control state~$q'$. Such a transition
changes instantaneous description $\langle q,xu,yv\rangle$ to
$\langle q',u,zv\rangle$, where the first component of an $ID$ is the
control state, the second is the unread remainder of the input string,
and the third is the stack content, head on left.

\medskip
\display 40pt:{\bf (A)}:
[10 points.] Define a (finite) set of such transitions as
{\sl deterministic\/} if no $ID$ can be changed by more than one transition.
How can we test a PDM for determinism?

\medskip
\display 40pt:{\bf (B)}:
[10 points.] In such a PDM, suppose $q\in Q$, no transitions both begin and
end with~$q$, $q\notin S$, $q\notin F$. Suppose we wish to eliminate
state~$q$, by combining such pairs as, say
$$\langle q↓1,x↓1,y↓1,z↓1,q\rangle\,\langle q,x↓2,y↓2,z↓2,q↓2\rangle$$
into a single transition. What conditions are necessary in order to
combine such a pair? Give an algorithm to combine such pairs.

\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
May 6, 1986.
%revised date;
%subsequently revised.

\bye